home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Oh!X 2001 Spring
/
Oh!X 2001 Spring Special CD-ROM (Japan).7z
/
Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin
/
PUZZLE
/
Puz02
/
oshidori.c
< prev
next >
Wrap
C/C++ Source or Header
|
2000-06-28
|
3KB
|
132 lines
/*
* oshidori.c : パズル「おしどり」の解法
*
* Copyright (C) 2000 by Makoto Hiroi
*
*/
/*
黒白黒白黒白空空 -> 黒黒黒白白白空空
動かせる駒はペア単位である
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define S 0
#define B 1
#define W 2
#define SIZE 8
/* 状態の最大値 */
#define MAX_STATE 140
/* 状態 */
char state[MAX_STATE + 1][SIZE]; /* +1 はワーク領域 */
char space_postion[MAX_STATE];
short prev_state[MAX_STATE];
/* 初期状態 */
char initial_state[SIZE] = {
B, W, B, W, B, W, S, S
};
/* 最終状態 */
char final_state[SIZE] = {
B, B, B, W, W, W, S, S
};
/* 手順の表示 */
void print_answer( int n )
{
int i;
if( n != 0 ) print_answer( prev_state[n] );
for( i = 0; i < SIZE; i++ ){
switch( state[n][i] ){
case S:
printf("空 "); break;
case B:
printf("黒 "); break;
case W:
printf("白 "); break;
}
}
printf("\n");
}
/* 同じ状態をチェックする */
int check_same_state( int n )
{
/* とりあえず単純な線形探索 */
int i;
for( i = 0; i < n; i++ ){
if( !memcmp( state[i], state[n], SIZE ) ) return TRUE;
}
return FALSE;
}
/* 番人を使う方法 */
int check_same_state1( int n )
{
int i = 0;
while( memcmp( state[i], state[n], SIZE ) ) i++;
return (i != n) ? TRUE : FALSE;
}
/* 石の移動 */
void move_stone( int front, int rear, int dest )
{
int j = space_postion[front];
memcpy( state[rear], state[front], SIZE );
state[rear][j] = state[front][dest];
state[rear][j + 1] = state[front][dest + 1];
state[rear][dest] = S;
state[rear][dest + 1] = S;
space_postion[rear] = dest;
prev_state[rear] = front;
}
/* 探索関数 */
void search( void )
{
int front = 0, rear = 1;
/* 初期化 */
memcpy( state[0], initial_state, SIZE );
prev_state[0] = -1;
space_postion[0] = 6;
while( front < rear ){
int i;
/* 移動 (0 から 6 までチェック) */
for( i = 0; i < SIZE - 1; i++ ){
if( state[front][i] && state[front][i + 1] ){
/* 移動可能 */
move_stone( front, rear, i );
/* チェックする */
if( !memcmp( state[rear], final_state, SIZE ) ){
/* 解けた */
print_answer( rear );
printf("状態数 %d 個\n", rear );
return;
} else if( !check_same_state1( rear ) ){
/* 同じ状態はない */
rear++;
}
}
}
front++;
}
}
int main()
{
search();
return 0;
}
/* end of file */